package q887_superEggDrop;

public class Solution_2 {
    /*
    逆向思维 比较难以想到的方法了
    反过来想这个问题：如果我们可以做 t 次操作，而且有 k 个鸡蛋，
    那么我们能找到答案的最高的 n 是多少？
    我们设 f(t, k) 为在上述条件下的 n。
    如果我们求出了所有的 f(t, k)，那么只需要找出最小的满足 (t,k)≥n 的 t。

     */
    public int superEggDrop(int k, int n) {
        if (n == 1) {
            return 1;
        }
        int[][] f = new int[n + 1][k + 1];
        for (int i = 1; i <= k; ++i) {
            f[1][i] = 1;
        }
        int ans = -1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[i][j] = 1 + f[i - 1][j - 1] + f[i - 1][j];
            }
            if (f[i][k] >= n) {
                ans = i;
                break;
            }
        }
        return ans;
    }

}
